/*
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
*/

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (!prices.size()) return 0;
        vector<int> p1(prices.size(), 0);
        vector<int> p2(prices.size(), 0);
        int tmpmin = prices[0], m1 = INT_MIN;
        // compute first transaction gain
        for (int i=1; i < prices.size(); i++) {
            int gain = prices[i] - tmpmin;
            if (gain > m1) m1 = gain;
            p1[i] = m1; tmpmin = min(tmpmin, prices[i]);
        }
        // compute second transaction gain
        int tmpmax = prices[prices.size()-1], m2 = INT_MIN;
        for (int i=prices.size()-2; i>=0; i--) {
            int gain = tmpmax - prices[i];
            if (gain > m2) m2 = gain;
            p2[i] = m2; tmpmax = max(tmpmax, prices[i]);
        }
        // compute combo value of two transactions
        int maxp = INT_MIN;
        for (int i = 0; i < prices.size(); i++) {
            int mcombo = max(p1[i], p2[i]);
            mcombo = max(mcombo, p1[i]+p2[i]);
            if (mcombo > maxp) maxp = mcombo;
        }
        return maxp;
        
    }
};
